package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class MaximumLevelSumOfABinaryTree {
	
	//方法一：BFS
    public int maxLevelSum(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0, minLevel = 0, maxSum = Integer.MIN_VALUE;
        while(!queue.isEmpty()) {
        	level++;
        	int sum = 0;
        	for(int size = queue.size(); size > 0; size--) {
        		TreeNode node = queue.poll();
        		sum += node.val;
        		if(node.left != null)
        			queue.offer(node.left);
        		
        		if(node.right != null)
        			queue.offer(node.right);
        	}
        	if(sum > maxSum) {
        		minLevel = level;
        		maxSum = sum;
        	}
        }
        return minLevel;
    }
    
    //方法一：DFS
    public int maxLevelSum2(TreeNode root) {
    	List<Integer> tmp = new ArrayList<>();
    	int minLevel = 0, maxSum = Integer.MIN_VALUE;
    	maxLevelSum2(root, 0, tmp);
    	for(int i = 0; i < tmp.size(); i++) {
    		int sum = tmp.get(i);
    		if(sum > maxSum) {
        		minLevel = i + 1;
        		maxSum = sum;
    		}
    	}
    	return minLevel;
    }
    
    private void maxLevelSum2(TreeNode node, int level, List<Integer> tmp) {
    	if(node == null) return;

    	if(tmp.size() == level) {
    		tmp.add(node.val);
    	}else {
    		int sum = tmp.get(level) + node.val;
    		tmp.set(level, sum);
    	}
    	
    	maxLevelSum2(node.left, level + 1, tmp);
    	maxLevelSum2(node.right, level + 1, tmp);
    }
    
}
